package com.atguigu.Dijkstra;

import java.util.Arrays;

/**
 * @author tbwtbw
 * @create 2021-11-27 14:45
 */
public class Dijkstra {

    static final int N = 65535;// 表示不可以连接

    public static void main(String[] args) {
        char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'Q' };
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        matrix[0]=new int[]{N,5,7,N,N,N,2};
        matrix[1]=new int[]{5,N,N,9,N,N,3};
        matrix[2]=new int[]{7,N,N,N,8,N,N};
        matrix[3]=new int[]{N,9,N,N,N,4,N};
        matrix[4]=new int[]{N,N,8,N,N,5,4};
        matrix[5]=new int[]{N,N,N,4,5,N,6};
        matrix[6]=new int[]{2,3,N,N,4,6,N};

        dijkstra(matrix,6);
    }

    public static void dijkstra(int[][] matrix,int start){

        int[] distance = new int[matrix.length];//表示起始点到各点的最短距离
        boolean[] visited = new boolean[matrix.length];//被访问过表示源点到它的最短距离已经找到
        for (int i = 0; i < matrix.length; i++) {
            if (start != i){
                distance[i] = matrix[start][i];
                visited[i] = false;
            }else {
                distance[i] = 0;
                visited[i] = true;//初始化，将起始顶点到邻接点的距离填入，自己到自己记为0。并标记为已访问
            }
        }


        int k = 0;
        for (int i = 1; i < matrix.length; i++) {//按照广度优先和贪心的思想，处理剩下的结点，这里i没有什么用，只是表示要处理几次
            int min = N;
            for (int j = 0; j < matrix.length; j++) {//按照贪心策略，找距离源点距离最近的点
                if (j != start && !visited[j] && distance[j] < min){
                    min = distance[j];
                    k = j;
                }
            }
            visited[k] = true;//这时候 k 是距离源点最近的点，标记为已访问,接下来比较源点以不以k为中转到各点的距离

            for (int j = 0; j < matrix.length; j++) {
                if (!visited[j] && distance[k] + matrix[k][j] < distance[j]){//被访问过了就不考虑了
                    distance[j] = distance[k] + matrix[k][j];
                }
            }
        }
        System.out.println(Arrays.toString(distance));
    }
}
